namespace Comb {
	int mo, phi;
	int pow_mod(int x, int k, int MOD = -1) {
		if (MOD == -1) MOD = mo;
		int ans = 1;
		while (k) {
			if (k&1) ans = 1LL * ans * x % MOD;
			x = 1LL * x * x % MOD;
			k >>= 1;
		}
		return ans;
	}
	//b * p^a
	struct atom {
		int a, b;
		atom() {}
		atom(int a, int b) : a(a), b(b) {}
		atom operator * (const atom& c) const {
			return atom(a + c.a, 1LL * b * c.b % mo);
		}
		atom operator / (const atom& c) const {
			return atom(a - c.a, 1LL * b * pow_mod(c.b, phi - 1) % mo);
		}
		int get(int q, int p) {
			if (a >= q) return 0;
			return 1LL * pow_mod(p, a) * b % mo;
		}
	} f[N], x[N];
	int get(int n, int m, int p, int q, int Mo) {
		mo = Mo; phi = Mo / p * (p - 1);
		f[0] = atom(0, 1);
		for (int i = 1; i <= n; i++) {
			int k1 = i, k2 = 0;
			while (k1 % p == 0) k1 /= p, k2++;
			x[i] = atom(k2, k1);
		}
		for (int i = 1; i <= n; i++) f[i] = f[i - 1] * x[i];
		atom u = f[n] / (f[m] * f[n - m]);
		return u.get(q, p);
	}

	int pri[20], w[20], ph[20];

	int C(int n, int m, int p) {
		if (n < m || n < 0 || m < 0) return 0;
		int sz = 0;
		for (int i = 2; i * i <= p; i++) {
			if (p % i == 0) {
				sz++; pri[sz] = 1; int cnt = 0;
				while (p % i == 0) {pri[sz] *= i; cnt++; p /= i;}
				w[sz] = get(n, m, i, cnt, pri[sz]);
				ph[sz] = pri[sz] / i * (i - 1);
			}
		}
		if (p > 1) {sz++; pri[sz] = p; w[sz] = get(n, m, p, 1, pri[sz]); ph[sz] = p - 1;}
		for (int i = 1; i < sz; i++) {
			int k1 = pow_mod(pri[i], ph[i + 1] - 1, pri[i + 1]);
			int k2 = pow_mod(pri[i + 1], ph[i] - 1, pri[i]);
			mo = pri[i] * pri[i + 1];
			w[i + 1] = (1LL * w[i] * k2 % mo * pri[i + 1] + 1LL * w[i + 1] * k1 % mo * pri[i]) % mo;
			pri[i + 1] = mo; ph[i + 1] *= ph[i];
		}
		return w[sz];
	}
}
